﻿#define _CRT_SECURE_NO_WARNINGS

//升序
#include "Heap.h"


void Swap(int* e1, int* e2)
{
	int temp = *e1;
	*e1 = *e2;
	*e2 = temp;
}

//升序建大堆； Top k 小堆
void AdjustUp(int* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	//child==0，说明已经向上与父亲调整好了，跳出。---- 图
	while (child > 0)
	{
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;//交换后继续向上调整，原先父亲是现在孩子
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//升序--大堆 ; Top k 小堆
void AdjustDown(int* arr, int size, int parent)
{
	assert(arr);

	//先假设左孩子是大数，如果不对，再调整
	int child = parent * 2 + 1;

	//左孩子==size越界，说明父亲是叶子，没孩子，向下调整结束了
	while (child < size)
	{
		//右孩子==左孩子+1，左孩子是最后一个节点时，右孩子会越界
		if (child + 1 < size && arr[child] > arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;//交换后继续向下调整，原先孩子是现在父亲
			child = parent * 2 - 1;//先假设左孩子是大数，如果不对，再调整
		}
		else
		{
			//已是堆，无需再向下调整
			break;
		}
	}
}

//结构体初始化
void HPInit(HP* php)
{
	assert(php);
	
	php->arr = NULL;
	php->size = 0;
	php->capacity = 0;
}

//插入堆数据
void HPPush(HP* php, HeapDataType x)
{
	assert(php);

	int newCapacity = (0 == php->capacity) ? 5 : 2 * php->capacity;
	HeapDataType* temp = (HeapDataType*)realloc(php->arr, newCapacity);//要给数组扩容用realloc
	if (NULL == temp)
	{
		perror("realloc file");
		exit(-1);//异常结束程序
	}
	php->arr = temp;
	php->capacity = newCapacity;

	//插入数据
	php->arr[php->size] = x;
	php->size++;
	//向上调整，保持小堆结构
	AdjustUp(php->arr, php->size-1);
}

////取堆顶
//HeapDataType HPTop(HP* php)
//{
//	assert(php);
//
//	return php
//}

//用向上调整建堆，进行堆排序
int* AdjustUpHeap_Sort(int* arr, int size)
{
	//在已给的数组上建堆，不再重新开辟空间
	//从第二个节点，也就是第一个孩子开始，向上调整建堆
	int i = 0;
	for (i = 1; i < size; i++)
	{
		AdjustUp(arr, i);
	}

	//堆排序 -- 升序。将最大值与最后一个节点交换，排好最大值。将当前堆顶向下调整使剩下的元素仍然是堆
	int n = size - 1;//表示元素下标
	//当n==0时说明只剩下了最后一个元素，不用再排了，顺着就排好了
	while (n)
	{
		Swap(&arr[0], &arr[n]);
		//当前n是已排好元素的下标，也是前面剩下元素的个数
		AdjustDown(arr, n, 0);
		n--;//得到剩余最后一个元素的下标，准备找次大值交换
	}

	return arr;
}


// 造数据
void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned int)time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}


//堆排序
void HeapSort(int* a, int n)
{
	//用向下调整法建堆
	int i = 0;
	//倒数第一个父亲就是最后一个节点(叶子)的父亲
	int n1 = n - 1;//最后一个元素的下标
	for (i = (n1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n1, i);//小堆
	}

	//堆排序——降序-小堆;
	while (n1)
	{
		Swap(&a[0], &a[n1]);
		//n也是下标n前面元素的个数
		AdjustDown(a, n1, 0);
		n1--;
	}

}
















